package com.alex.sort;

import java.util.Arrays;

/**
 * Describe: AlexP
 * Created by pengp on 2018/10/11.
 */
public class CountSort {
    public static int[] countSort(int[] array){
        //1、获取最大值
        int max = array[0];
        for(int num:array){
            if (num > max){
                max = num;
            }
        }
        //2、根据数列最大值确定统计数组的长度
        int[] countArray = new int[max+1];
        //3、遍历数列，填充数组
        for (int num:array){
            countArray[num]++;
        }
        //遍历统计数组，输出结果
        int index = 0;
        int[] sortedArray = new int[array.length];
        for (int i=0;i<countArray.length;i++){
            for (int j=0;j<countArray[i];j++){
                sortedArray[index++] = i;
            }
        }
        return sortedArray;
    }
    public static int[] countSortOptimize(int[] array){
        //1、获取最大值和最小值
        int max = array[0];
        int min = array[0];
        for(int num:array){
            if (num > max){
                max = num;
            }
            if(num< min){
                min = num;
            }
        }
        int d = max - min;
        //2、创建统计数组做并统计元素个数
        int[] countArray = new int[d+1];
        for (int num:array){
            countArray[num - min]++;
        }
        //3、统计数组做变形，后面的元素等于前面的元素之和
        int sum = 0;
        for(int i=0;i<countArray.length;i++){
            sum += countArray[i];
            countArray[i] = sum;
        }
        //4、倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组
        int[] sortedArray = new int[array.length];
        for (int i=array.length-1;i>=0;i--){
            sortedArray[countArray[array[i]-min]-1] = array[i];
            countArray[array[i] - min]--;
        }
        return sortedArray;
    }

    public static void main(String[] args) {
        int[] array = new int[]{4,4,6,5,3,2,8,1,7,5,6,0,10};
        int[] array2 = new int[]{94,94,96,95,93,92,98,91,97,95,96,90,100};
        int[] sortedArray = countSort(array);
        int[] sortedArray2 = countSortOptimize(array2);
        System.out.println(Arrays.toString(sortedArray));
        System.out.println(Arrays.toString(sortedArray2));
    }
}
